class Solution(object):
    def shortestDistanceColor(self, colors, queries):
        """
        :type colors: List[int]
        :type queries: List[List[int]]
        :rtype: List[int]
        """
        n = len(colors)
        m = len(queries)
        DP1 = [[-1 for _ in range(3)] for _ in range(n)]
        DP2 = [[-1 for _ in range(3)] for _ in range(n)]
        DP1[0][colors[0] - 1] = 0
        for i in range(1, n):
            for j in range(1, 4):
                if j == colors[i]:
                    DP1[i][j - 1] = 0
                else:
                    if DP1[i - 1][j - 1] >= 0:
                        DP1[i][j - 1] = DP1[i - 1][j - 1] + 1
        DP2[n - 1][colors[n - 1] - 1] = 0
        for i in range(n - 2, -1, -1):
            for j in range(1, 4):
                if j == colors[i]:
                    DP2[i][j - 1] = 0
                else:
                    if DP2[i + 1][j - 1] >= 0:
                        DP2[i][j - 1] = DP2[i + 1][j - 1] + 1
        for i in range(n):
            for j in range(3):
                if DP1[i][j] < 0:
                    if DP2[i][j] >= 0:
                        DP1[i][j] = DP2[i][j]
                else:
                    if 0 <= DP2[i][j] < DP1[i][j]:
                        DP1[i][j] = DP2[i][j]
        out = [0] * m
        for i in range(m):
            out[i] = DP1[queries[i][0]][queries[i][1] - 1]
        return out


data = Solution()
colors = [1, 1, 2, 1, 3, 2, 2, 3, 3]
queries = [[1, 3], [2, 2], [6, 1]]
print(data.shortestDistanceColor(colors, queries))
colors = [1]
queries = [[0, 1]]
print(data.shortestDistanceColor(colors, queries))
